package erfen;

/**
 * 用一次二分先找出最小值的位置  pivot ，这样  [0 … pivot-1]  与  [pivot … n-1]  都是严格升序的；
 * 再判断  target  落在哪一段，再对该段做一次普通二分即可。
 */
public class Solution_33 {

    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;

        // 1. 二分找最小值下标 pivot
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] > nums[right]) {
                left = mid + 1;          // 最小值在右侧
            } else {
                right = mid;             // 最小值在左侧或就是 mid
            }
        }
        int pivot = left;                // pivot 是最小值所在下标

        // 2. 判断 target 落在哪一段
        if (target >= nums[pivot] && target <= nums[n - 1]) {
            // 右半段 [pivot, n-1]
            left = pivot;
            right = n - 1;
        } else {
            // 左半段 [0, pivot-1]
            left = 0;
            right = pivot - 1;
        }

        // 3. 普通二分
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution_33 solution33 = new Solution_33();
        System.out.println(solution33.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 1));
    }
}
